#include"Maze.h"

void Maze::Stack::Push(TypeData x)
{
	if (_size + 1 >= _capacity)
	{
		int newcapacity = 2 * _capacity;
		TypeData* tmp = (TypeData*)realloc(_a, newcapacity*sizeof(TypeData));
		assert(tmp);
		_a = tmp;
		_capacity = newcapacity;
	}
	
	_a[++_size]._x = x._x;
	_a[_size]._y = x._y;
}

void Maze::Print()
{
	for (int i = 0; i < _rows; i++)
	{
		for (int j = 0; j < _cols; j++)
		{
			cout << _pool[i][j] << " ";
		}
		cout << endl;
	}
}

bool Maze::IsNodeTure(int x,int y)
{
	if (y >= 0 && y < _rows
		&& x >= 0 && x < _cols
		&& _pool[y][x] == 0)
	{
		return 1;
	}
	else
		return 0;
}

bool Maze::GetPassage(int x,int y)
{
	Node node(x, y);
	
	_stack.Push(node);

	if (x == _cols - 1 && y == 0)
	{
		if (_minstack.IsEmpity() || _minstack.GetSize() > _stack.GetSize())
		{
			_minstack = _stack;
		}
	}

	_pool[y][x] = -1;
	//up
	if (IsNodeTure(x,y - 1))
	{
		GetPassage(x, y - 1);

	}
	//down
	if (IsNodeTure(x,y + 1))
	{
		GetPassage(x, y + 1);

	}
	//left
	if (IsNodeTure(x - 1,y))
	{
		GetPassage(x - 1, y);

	}
	//right
	if (IsNodeTure(x + 1,y))
	{
		GetPassage(x + 1, y);

	}

	_stack.Pop();
	_pool[y][x] = 0;
	if (_minstack.IsEmpity())
		return 0;
	else
		return 1;
}

Maze::Stack& Maze::Stack::operator=(Maze::Stack& s)
{
	if (_a != nullptr)
	{
		free(_a);
		_a = nullptr;
	}
	int size = s.GetSize();
	_a = (TypeData*)malloc(sizeof(TypeData) * s.GetCapacity());
	assert(_a);
	_size = size;
	_capacity = s.GetCapacity();
	for (int i = 0; i <= size; i++)
	{
		_a[i]._x = s._a[i]._x;
		_a[i]._y = s._a[i]._y;
	}
	return *this;
}

void Maze::Print_Passage()
{
	Stack newstack, oldstack = _minstack;
	while (!oldstack.IsEmpity())
	{
		newstack.Push(oldstack.Top());
		oldstack.Pop();
	}
	while (!newstack.IsEmpity())
	{
		printf("(%d,%d)\n", newstack.Top()._x, newstack.Top()._y);
		newstack.Pop();
	}
}

Maze::Maze()
{
	cin >> _rows >> _cols;
	_pool = (int**)malloc(sizeof(int*) * _rows);
	assert(_pool);
	for (int i = 0; i < _rows; i++)
	{
		_pool[i] = (int*)malloc(sizeof(int) * _cols);
		assert(_pool[i]);
	}

	for (int i = 0; i < _rows; i++)
	{
		for (int j = 0; j < _cols; j++)
		{
			cin >> _pool[i][j];
		}
	}
	_node._x = _node._y = 0;
}






